package com.lee.algorithm.recursion;

import java.util.HashMap;
import java.util.Map;

/***
 * @description: N 皇后问题
 *      不能共行、不能共列、不能共斜线
 * @author : 青石路
 * @date: 2021/12/15 20:43
 */
public class NQueen {

    public static int num(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];  // record[i] -> 索引i表示i行的皇后，record[i]记录的是列值（i行的皇后放到了哪一列）
        return process(0, record, n);
    }

    /**
     *
     * @param i 试着放i行的皇后，record[0...i-1]已放好
     * @param record 索引表示皇后，索引上的值表示皇后放的列
     * @param n 皇后个数，也表示有多少行
     * @return
     */
    public static int process(int i, int[] record, int n) {
        if (i == n) {
            return 1;
        }
        int res = 0;
        for (int j = 0; j<n; j++) { // 将i行的皇后，在所有列上进行尝试
            if(isValid(record, i, j)) { // 有效则把i行的皇后放到j列上
                record[i] = j;
                res += process(i+1, record, n); // 继续尝试放 i+1 行的皇后
            }
        }
        return res;
    }

    /**
     * 返回 i 行皇后放在 j 列，是否有效
     *
     * 需要考虑 record[0...i-1]
     * @param record
     * @param i
     * @param j
     * @return
     */
    public static boolean isValid(int[] record, int i, int j) {
        for (int k=0; k<i; k++) {   // k 表示行
            if (j == record[k]      // 同列
                    || Math.abs(record[k] - j) == Math.abs(i - k)   // 同斜线（点(record[k],i) 与 点(j,k) 是否同斜线的判断）
            ) {
                return false;
            }
        }
        return true;
    }

    /**
     * 相比于 num，做了常数项的优化，指标项还是一样的
     * @param n
     * @return
     */
    public static int numPlus(int n) {
        if (n < 1 || n > 32) {      // 如若超过 32，int n 改成 long n
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;  // 比如 n=9，limit的二进制位后9位都是1，前面都是0
        return processPlus(limit, 0, 0, 0);
    }

    /**
     * 通过位运算进行优化
     * 利用位运算的特性代替 record 的检查
     *
     * >>> 无符号右移，忽略符号位，空位都以0补齐
     *
     * @param limit
     * @param colLim    列的限制，1的位置不能放皇后，0的位置可以
     * @param leftDiaLim    左斜线的限制，1的位置不能放皇后，0的位置可以
     * @param rightDiaLim   右斜线的限制，1的位置不能放皇后，0的位置可以
     * @return
     */
    private static int processPlus(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {      // 所有皇后都填上了，该方案可行
            return 1;
        }

        // 可以放皇后的位置体现在pos对应的二进制位上，1表示可以放，0表示不能放
        // 取反之后的高位全是1，与 limit 进行 & 运算后，高位变成 0
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));

        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);        // 提取 pos 最右侧的 1，表示该位置放皇后
            pos = pos - mostRightOne;            // pos 最右侧 1 尝试放了皇后，将该位置置成 0
            // 递归一次，表示处理下一行
            res += processPlus(limit, colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int nums = numPlus(15);
        long end = System.currentTimeMillis();
        System.out.println("共有 " + nums + " 种摆法, 共耗时 " + (end - start) + " 毫秒");

        start = System.currentTimeMillis();
        nums = num(15);
        end = System.currentTimeMillis();
        System.out.println("共有 " + nums + " 种摆法, 共耗时 " + (end - start) + " 毫秒");
    }
}
